package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhangjy
 * @description 二叉搜索树中的搜索
 * @date 2025/4/23 11:36
 */
public class SearchBST_700 {

    /**
     * 个解：dfs-迭代-先序
     * <p>
     * 思路：
     * 空节点入队
     */
    public TreeNode searchBST3(TreeNode root, int val) {
        if (root == null) return null;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode node = null;
        while (!queue.isEmpty()) {
            node = queue.poll();
            // 叶子节点
            if (node == null) return null;

            if (val == node.val) {
                return node;
            }
            if (val < node.val) {
                // val小，则遍历左子树
                queue.offer(node.left);
            } else {
                queue.offer(node.right);
            }
        }

        return node;
    }

    /**
     * 个解：dfs-迭代-先序
     * <p>
     * 比空节点入队，非空入队实现稍微复杂一点
     */
    public TreeNode searchBST2(TreeNode root, int val) {
        if (root == null) return null;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode node = null;
        while (!queue.isEmpty()) {
            node = queue.poll();

            if (val == node.val) {
                return node;
            }
            // 叶子节点
            if (node.left == null && node.right == null) {
                return null;
            }

            if (val < node.val) {
                // val小，则遍历左子树
                // 若空，表明找不到等于val的节点，直接返回null
                if (node.left == null) return null;
                // 非空入队
                queue.offer(node.left);
            } else {
                if (node.right == null) return null;
                queue.offer(node.right);
            }
        }

        return node;
    }

    /**
     * 个解：dfs-递归-先序
     * <p>
     * 思路：
     * 题目没有明确提示，表明该BST是一棵严格递增的搜索树，不存在相等的节点
     */
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;

        // 根
        if (root.val == val) return root;
        TreeNode node = null;
        if (val < root.val) {
            // 左
            node = searchBST(root.left, val);
        } else {
            // 右
            node = searchBST(root.right, val);
        }

        return node;
    }

}
